#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "BigDecimal.h"

#define MaxSize 1000

struct BigDecimal InputBD(char * s) {
    struct BigDecimal result;
    char integerPart[MaxSize];
    char decimalPart[MaxSize];
    int point = 0;
    int i;
    /* 利用小数点将实数分为整数和小数部分 */
    while (s[point] != '.' && point < strlen(s)) {
        point++;
    }
    assert(point < strlen(s) - 1);
    if (s[0] == '-') { /* 如果是负数整数部分从第二位开始 */
        for (i = 1; i < point; i++)
            integerPart[i - 1] = s[i];
        integerPart[i - 1] = '\0'; /* 末尾添加结束符 */
        result.sign = 1;
    }
    else {
        for (i = 0; i < point; i++)
            integerPart[i] = s[i];
        integerPart[point] = '\0';
        result.sign = 0;
    }
    for (i = point + 1; i < strlen(s); i++)
        decimalPart[i - point - 1] = s[i];
    decimalPart[i - point - 1] = '\0'; /* 末尾添加结束符 */
    result.integer = InputUBN(integerPart);
    result.decimal = _InputDecimal(decimalPart);

    return result;
}

struct BigDecimal AddBD(struct BigDecimal * pA, struct BigDecimal * pB) {
    /* 左加数为正数, 右加数为正数 */
    struct BigDecimal result;
    if (pA->sign == 0 && pB->sign == 0)
        result = _AddUBD(pA, pB);
    /* 左加数为正数, 右加数为负数 */
    if (pA->sign == 0 && pB->sign == 1) {
        if (_CompareUBD(pA, pB) >= 0) { /* 左加数的绝对值大于等于右加数的绝对值 */
            result = _SubUBD(pA, pB);
            result.sign = 0;
        }
        else { /* 左加数的绝对值小于右加数的绝对值 */
            result = _SubUBD(pB, pA);
            result.sign = 1;
        }
    }
    /* 左加数为负数, 右加数为正数 */
    if (pA->sign == 1 && pB->sign == 0) {
        if (_CompareUBD(pA, pB) > 0) { /* 左加数的绝对值大于右加数的绝对值 */
            result = _SubUBD(pA, pB);
            result.sign = 1;
        }
        else { /* 左加数的绝对值小于等于右加数的绝对值 */
            result = _SubUBD(pB, pA);
            result.sign = 0;
        }
    }
    if (pA->sign == 1 && pB->sign == 1) {
        result = _AddUBD(pA, pB);
        result.sign = 1;
    }
    return result;
}

struct BigDecimal SubBD(struct BigDecimal * pA, struct BigDecimal * pB) {
    struct BigDecimal result;
    if (pA->sign == 0 && pB->sign == 0)  { /* 被减数为正数, 减数为正数 */
        if (_CompareUBD(pA, pB) >= 0) { /* 被减数的绝对值大于等于减数的绝对值 */
            result = _SubUBD(pA, pB);
            result.sign = 0;
        }
        else { /* 被减数的绝对值小于减数的绝对值 */
            result = _SubUBD(pB, pA);
            result.sign = 1;
        }
    }
    if (pA->sign == 0 && pB->sign == 1) { /* 被减数为正数, 减数为负数 */
        result = _AddUBD(pA, pB);
        result.sign = 0;
    }
    if (pA->sign == 1 && pB->sign == 0) { /* 被减数为负数, 减数为正数 */
        result = _AddUBD(pA, pB);
        result.sign = 1;
    }
    if (pA->sign == 1 && pB->sign == 1) { /* 被减数为负数, 减数为负数 */
        if (_CompareUBD(pA, pB) > 0) { /* 被减数的绝对值大于减数的绝对值 */
            result = _SubUBD(pA, pB);
            result.sign = 1;
        }
        else { /* 被减数的绝对值小于等于减数的绝对值 */
            result = _SubUBD(pB, pA);
            result.sign = 0;
        }
    }
    return result;
}

struct BigDecimal MultiplyBD(struct BigDecimal * pA, struct BigDecimal * pB) {
    struct BigDecimal result;
    result = _MultiplyUBD(pA, pB);
    /* 左乘数和右乘数同号 */
    if (pA->sign == 0 && pB->sign == 0 || pA->sign == 1 && pB->sign == 1)
        result.sign = 0;
    else /* 左乘数和右乘数异号 */
        result.sign = 1;
    return result;
}

struct BigDecimal DivBD(struct BigDecimal * pA, struct BigDecimal * pB, int R) {
    struct BigDecimal result;
    result = _DivUBD(pA, pB, R);
    /* 被除数与除数同号 */
    if (pA->sign == 0 && pB->sign == 0 || pA->sign == 1 && pB->sign == 1)
        result.sign = 0;
    else /* 被除数与除数异号 */
        result.sign = 1;
    return result;
}

void DestroyBD(struct BigDecimal * pBD) {
    DestroyUBN(&pBD->integer);
    DestroyUBN(&pBD->decimal);
}

void PrintBD(struct BigDecimal bd) {
    if (bd.sign == 1) printf("-");
    PrintUBN(bd.integer);
    printf(".");
    PrintUBN(bd.decimal);
    printf("\n");
}

struct BigDecimal _AddUBD(struct BigDecimal *pA, struct BigDecimal *pB) {
    struct BigDecimal result;
    struct UBigNumber integer, decimal;
    int iCarry;
    decimal = _AddDecimal(&pA->decimal, &pB->decimal, &iCarry);
    integer = _AddInteger(&pA->integer, &pB->integer, iCarry);
    result.integer = integer;
    result.decimal = decimal;
    result.sign = 0;
    return result;
}

struct UBigNumber _AddInteger(struct UBigNumber * pA, struct UBigNumber * pB, int iCarry) {
    struct UBigNumber result, * pResult = &result;
    _InitUBN(pResult);
    struct Node * p1, * p2;
    p1 = pA->pTail;
    p2 = pB->pTail;
    while (p1 != pA->pHead && p2 != pB->pHead)
    {
        int digit = p1->digit + p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }
    while (p1 != pA->pHead)
    {
        int digit = p1->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    while (p2 != pB->pHead)
    {
        int digit = p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p2 = p2->prev;
    }
    if (iCarry != 0)
        _AppendFrontDigit(pResult, iCarry);
    return result;
}

struct BigDecimal _SubUBD(struct BigDecimal * pA, struct BigDecimal * pB) {
    struct BigDecimal result;
    struct UBigNumber integer, decimal;
    int iCarry;
    decimal = _SubDecimal(&pA->decimal, &pB->decimal, &iCarry);
    integer = _SubInteger(&pA->integer, &pB->integer, iCarry);
    result.integer = integer;
    result.decimal = decimal;
    result.sign = 0;
    return result;
}

struct UBigNumber _AddDecimal(struct UBigNumber * pA, struct UBigNumber * pB, int * piCarry) {
    struct UBigNumber result, * pResult = &result;
    _InitUBN(pResult);
    _alignDecimal(pA, pB);
    int iCarry = 0;
    struct Node * p1, * p2;
    p1 = pA->pTail;
    p2 = pB->pTail;
    while (p1 != pA->pHead && p2 != pB->pHead)
    {
        int digit = p1->digit + p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }

    *piCarry = iCarry;
    return result;
}

struct UBigNumber _SubInteger(struct UBigNumber * pA, struct UBigNumber * pB, int iCarry) {
    struct UBigNumber result;
    _InitUBN(&result);
    struct Node * p1, *p2;
    p1 = pA->pTail; // 从低位开始处理
    p2 = pB->pTail;
    while (p1 != pA->pHead && p2 != pB->pHead) // 两数相同位处理
    {
        int digit = p1->digit - p2->digit + iCarry;
        iCarry = 0;
        if (digit < 0)
        {
            digit += 10; // 当前结果位
            iCarry = -1; // 新借位
        }
        _AppendFrontDigit(&result, digit); // 添加结果最高位
        p1 = p1->prev; // 准备处理前一位
        p2 = p2->prev;
    }
    assert(p2 == pB->pHead);
    while (p1 != pA->pHead) // 第 1 大数剩余位处理
    {
        int digit = p1->digit + iCarry;
        iCarry = 0;
        if (digit < 0)
        {
            digit += 10; // 当前结果位
            iCarry = -1; // 新借位
        }
        _AppendFrontDigit(&result, digit); // 添加至结果最高位
        p1 = p1->prev; // 准备处理前一位
    }
    assert(iCarry == 0);
    _Normalize(&result);
    return result;
}

struct UBigNumber _SubDecimal(struct UBigNumber * pA, struct UBigNumber * pB, int * piCarry) {
    struct UBigNumber result;
    _InitUBN(&result);
    _alignDecimal(pA, pB);
    int iCarry = 0; // 借位, 初始 0
    struct Node * p1, *p2;
    p1 = pA->pTail; // 从低位开始处理
    p2 = pB->pTail;
    while (p1 != pA->pHead && p2 != pB->pHead) // 两数相同位处理
    {
        int digit = p1->digit - p2->digit + iCarry;
        iCarry = 0;
        if (digit < 0)
        {
            digit += 10; // 当前结果位
            iCarry = -1; // 新借位
        }
        _AppendFrontDigit(&result, digit); // 添加结果最高位
        p1 = p1->prev; // 准备处理前一位
        p2 = p2->prev;
    }
    *piCarry = iCarry;
    _NormalizeDecimal(&result);
    return result;
}

struct BigDecimal _MultiplyUBD(struct BigDecimal * pA, struct BigDecimal * pB) {
    struct BigDecimal result;
    struct UBigNumber totalA = _Concat(&pA->integer,&pA->decimal);
    struct UBigNumber totalB = _Concat(&pB->integer, &pB->decimal);
    int cutPoint = pA->decimal.digitCount + pB->decimal.digitCount; /* 结果的小数点位数 */
    struct UBigNumber tempResult = MultiplyUBN(&totalA, &totalB); /* 临时存储未加小数点的乘法结果 */
    struct UBigNumber integer = _FetchSub(&tempResult, 0, tempResult.digitCount - cutPoint);
    struct UBigNumber decimal = _FetchSub(&tempResult, tempResult.digitCount - cutPoint, tempResult.digitCount);
    _NormalizeDecimal(&decimal);
    result.integer = integer;
    result.decimal = decimal;
    result.sign = 0;

    DestroyUBN(&totalA);
    DestroyUBN(&totalB);
    DestroyUBN(&tempResult);
    return result;
}

struct BigDecimal _DivUBD(struct BigDecimal * pA, struct BigDecimal * pB, int R) {
    /* 利用减法来代替除法 */
    struct BigDecimal result;
    struct UBigNumber integer, decimal;
    struct UBigNumber totalA, totalB; /* 被除数和除数 */
    struct UBigNumber tempA; /* 临时存储被除数, 方便运算 */
    struct UBigNumber tempResult, calResult; /* 存储放置小数点前的结果, 存储中间量方便运算 */
    struct UBigNumber One;
    int zeroNeed; /* 将被除数和除数转换为整数后,小数点后位数较少的数需要补的 0 的数量 */
    totalA = _Concat(&pA->integer, &pA->decimal);
    totalB = _Concat(&pB->integer, &pB->decimal);
    assert(totalB.pHead->next->digit); /* 除数为零报错 */
    if (totalA.pHead->next == 0) { /* 被除数为零特殊处理降低计算复杂度 */
        _AppendDigit(&result.integer, 0);
        _AppendDigit(&result.decimal, 0);
        result.sign = 0;
        return result;
    }

    if (pA->decimal.digitCount > pB->decimal.digitCount) {
        zeroNeed = pA->decimal.digitCount - pB->decimal.digitCount;
        for (int i = 0; i < zeroNeed; i++)
            _AppendDigit(&totalB, 0);
    }
    if (pA->decimal.digitCount < pB->decimal.digitCount) {
        zeroNeed = pB->decimal.digitCount - pA->decimal.digitCount;
        for (int i = 0; i < zeroNeed; i++)
            _AppendDigit(&totalA, 0);
    }
    for (int i = 0; i < R; i++)
        _AppendDigit(&totalA, 0);

    /* 初始化结果为 0 */
    _InitUBN(&tempResult);
    _AppendDigit(&tempResult, 0);
    /* 初始化计数器增量为 1 */
    _InitUBN(&One);
    _AppendDigit(&One, 1);
    while (_CompareUBN(&totalA, &totalB) == 1) {
        tempA = SubUBN(&totalA, &totalB);
        DestroyUBN(&totalA); /* 防止替换被除数后内存泄漏 */
        totalA = tempA;
        /* 结果计数器自增 */
        calResult = AddUBN(&tempResult, &One);
        DestroyUBN(&tempResult);
        tempResult = calResult;
    }
    /* 结果只有小数部分 */
    if (tempResult.digitCount <= R) {
        int decimalZeroNeed = R - tempResult.digitCount;
        for (int i = 0; i < decimalZeroNeed; i++)
            _AppendFrontDigit(&tempResult, 0);
        decimal = _FetchSub(&tempResult, 0, R);
        _NormalizeDecimal(&decimal);
        _InitUBN(&integer);
        _AppendDigit(&integer, 0);
    }
    else { /* 结果既有整数部分也有小数部分 */
        integer = _FetchSub(&tempResult, 0, tempResult.digitCount - R);
        decimal = _FetchSub(&tempResult, tempResult.digitCount - R, tempResult.digitCount);
    }

    result.integer = integer;
    result.decimal = decimal;
    result.sign = 0;

    DestroyUBN(&totalA);
    DestroyUBN(&totalB);
    DestroyUBN(&tempResult);
    DestroyUBN(&One);

    return result;
}

void _NormalizeDecimal(struct UBigNumber * pUBN)
{
    if (pUBN->digitCount == 0)
        _AppendDigit(pUBN, 0);
    while (pUBN->digitCount > 1 && pUBN->pTail->digit == 0)
    {   // 去除低位多余的 0
        struct Node *p;
        p = pUBN->pTail; // 待删除结点
        pUBN->pTail = p->prev;
        p->prev->next = NULL; // 正向链表中删除
        free(p); // 释放结点
        --pUBN->digitCount; // 调整位数
    }
}

void _alignDecimal(struct UBigNumber * pA, struct UBigNumber * pB) {
    int bits;
    /* 本身位数相等无需对齐 */
    if (pA->digitCount == pB->digitCount) return;

    if (pA->digitCount > pB->digitCount) {
        bits = pA->digitCount - pB->digitCount;
        for (int i = 0; i < bits; i++)
            _AppendDecimalDigit(pB, 0);
    }
    else {
        bits = pB->digitCount - pA->digitCount;
        for (int i = 0; i < bits; i++)
            _AppendDecimalDigit(pA, 0);
    }
}

struct UBigNumber _InputDecimal(char * s) {
    struct UBigNumber result;
    _InitUBN(&result);
    for (int i = 0; i < strlen(s); i++)
        _AppendDecimalDigit(&result, s[i] - '0');
    _NormalizeDecimal(&result);
    return result;
}

void _AppendDecimalDigit(struct UBigNumber * pUBN, int digit) {
    struct Node *p = _NewNode(); // 申请新结点
    p->digit = digit; // 设置结点数值
    p->next = NULL; // 修改双向链表, 将新结点添加到尾部
    p->prev = pUBN->pTail;
    pUBN->pTail->next = p;
    pUBN->pTail = p;
    ++pUBN->digitCount;
}

struct UBigNumber _Concat(struct UBigNumber * pA, struct UBigNumber * pB) {
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    struct Node * p = pA->pHead->next; /* 从 A 的开头复制数字 */
    while (p != pA->pTail) {
        _AppendDigit(pResult, p->digit);
        p = p->next;
    }
    _AppendDigit(pResult, p->digit);
    p = pB->pHead->next; /* 从 B 的开头复制数字 */
    while (p != pB->pTail) {
        _AppendDigit(pResult, p->digit);
        p = p->next;
    }
    _AppendDigit(pResult, p->digit);
    _Normalize(pResult);
    return result;
}

int _CompareUBN(struct UBigNumber * pA, struct UBigNumber * pB) {
    if (pA->digitCount > pB->digitCount) return 1;
    else if (pA->digitCount < pB->digitCount) return -1;
    else {
        struct Node * p1, * p2;
        p1 = pA->pHead->next; // 从高位开始处理
        p2 = pB->pHead->next;
        while (p1 != NULL && p2 != NULL) {
            if (p1->digit > p2->digit) return 1;
            else if (p1->digit < p2->digit) return -1;
            else {
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        return 0;
    }
}

int _CompareUBD(struct BigDecimal * pA, struct BigDecimal * pB) {
    if (pA->integer.digitCount > pB->integer.digitCount) return 1;
    else if (pA->integer.digitCount < pB->integer.digitCount) return -1;
    else {
        struct Node * p1, * p2;
        p1 = pA->integer.pHead->next;
        p2 = pB->integer.pHead->next;
        while (p1 != NULL && p2 != NULL) {
            if (p1->digit > p2->digit) return 1;
            else if (p1->digit < p2->digit) return -1;
            else {
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        p1 = pA->decimal.pHead->next;
        p2 = pB->decimal.pHead->next;
        while (p1 != NULL && p2 != NULL) {
            if (p1->digit > p2->digit) return 1;
            else if (p1->digit < p2->digit) return -1;
            else {
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        if (p1 == NULL && p2 == NULL) return 0;
        else if (p1 != NULL && p2 == NULL)  return 1;
        else return -1;
    }
}
